МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«Национальный исследовательский ядерный университет «МИФИ»
Обнинский институт атомной энергетики –
филиал федерального государственного автономного образовательного учреждения высшего образования
«Национальный исследовательский ядерный университет «МИФИ»
(ИАТЭ НИЯУ МИФИ)

Одобрено УМС ИАТЭ НИЯУ МИФИ,
Протокол №2-8/2021 От 30.08.2021

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
( Наименование дисциплины)

01.03.02 – Прикладная математика и информатика
(Код (шифр), наименование направления подготовки (специальности) ФГОС)

Прикладная информатика
(Профиль направления)

Название программы бакалавриата

бакалавр
(Квалификация (степень) выпускника)

очная
Форма обучения (очная, очно-заочная (вечерняя), заочная)

г. Обнинск 20 21 г.

Программа составлена в соответствии с требованиями образовательного стандарта высшего образования национального исследовательского ядерного университета «МИФИ» по направлению подготовки 01.03.02 – Прикладная математика и информатика, приказа Минобрнауки России №1367 от 19.12.2013 г.

Автор(ы)

З.Х. Насыров, доцент каф. ПМ

Рецензент_________  Заведующий лаб. Математических методов ФИАЦ ФГБУ «НПО «Тайфун», д.т.н Д. А. Камаев.

Программа рассмотрена на заседании отделения интеллектуальных кибернетических систем (О) (протокол № 5/7 от «30» июля  2021 г.)

Руководитель образовательной программы
01.03.02 – «Прикладная математика и информатика» 
_________________ 	С.В. Ермаков

«____»____________2021  г.

1.	Перечень планируемых результатов обучения по дисциплине, соотнесенных с планируемыми результатами освоения образовательной программы

Целью курса является  формирование необходимой математической базы по аксиоматическим теориям, нечеткой логике, рекурсивным функциям, машинам Тьюринга и формальным языкам для изучения последующих общепрофессиональных и специальных дисциплин.

Задачами изучения курса являются
Обучение студентов методам и мышлению, характерным для указанных выше разделов  математической  логики  и  теории  алгоритмов  на  основе  изучения
лекционного  материала  и  его  закрепления  с  помощью  решения  задач  и упражнений.

В	результате	освоения	ООП	бакалавриата	обучающийся	должен	овладеть следующими результатами обучения по дисциплине:

Коды
компетенций	Результаты освоения
ООП
Содержание компетенций	Перечень планируемых
результатов обучения по дисциплине	
ОПК-2	Способен использовать и адаптировать существующие математические методы и системы программирования для разработки и реализации алгоритмов решения прикладных задач	Знать: методы моделирования
аксиоматических и алгоритмических систем

Уметь: делать оценку сложности алгоритмов и анализировать результаты работы алгоритмов

Владеть: методами решения основных видов задач.	

2.	Место дисциплины в структуре ООП бакалавриата Дисциплина реализуется в рамках базовой  части.
Для освоения дисциплины необходимы компетенции, сформированные в рамках изучения следующих дисциплин: математический анализ, дискретная математика

Дисциплина изучается на 2 курсе в 4 семестре.

3.	Объем дисциплины в зачетных единицах с указанием количества академических часов, выделенных на контактную работу обучающихся с преподавателем (по видам занятий) и на самостоятельную работу обучающихся

Общая трудоемкость (объем) дисциплины составляет 4 зачетные единицы (з.е.), 144 академических часов.

3.1.	Объём дисциплины по видам учебных занятий (в часах)
Объем дисциплины	Всего часов	
	Очная форма обучения	
Общая трудоемкость дисциплины	144	
Контактная*	работа	обучающихся	с преподавателем
(по видам учебных занятий) (всего)	64	
Аудиторная работа (всего**):	48	
лекции	32	
семинары, практические занятия	16	
Внеаудиторная работа (всего**):	0	
групповая, индивидуальная консультация		
Самостоятельная	работа	обучающихся** (всего)	36	
Вид промежуточной аттестации обучающегося экзамен	54	

4.	Содержание дисциплины, структурированное по темам (разделам) с указанием отведенного на них количества академических часов и видов учебных занятий

4.1.	Разделы дисциплины и трудоемкость по видам учебных занятий (в академических часах)
Для очной формы обучения
№ п/п	Наименование раздела /темы дисциплины	Общая трудоём- кость
всего
(в часах)	Виды учебных занятий, включая самостоятельную работу обучающихся и
трудоемкость
(в часах)	Формы текущего контроля
успевае- мости	

			Аудиторные учебные занятия	

СРО		
			Лек	Сем/Пр	Лаб			
1.	Аксиоматические теории	15	10	4		1	Проверка на семинаре	
2.	Нечеткая логика и нечеткие множес- тва	4	2	2		0	Проверка на семинаре	
3.	Рекурсивные функции	11	6	4		1	Проверка на семинаре	
4.	Машины Тьюринга	10	6	4		0	Проверка на семинаре	
5.	Формальные языки и грамматики	9	6	2		1	Проверка на семинаре	
6.	Сложность алгоритмов.	5	4	1		0	Проверка на семинаре	

4.2.	Содержание дисциплины, структурированное по разделам (темам)

Лекционный курс

№	Наименование раздела /темы дисциплины	Содержание	
1.	Аксиоматические теории	Понятие аксиоматической теории. Определение исчисления высказываний.	Теорема	дедукции,		теоремы	о	двойном отрицании,		доказательство		от	противного,		введение конъюнкции			и		закон	противоречия		в		исчислении высказываний.			Интерпретация		и			теорема	о непротиворечивости. Теорема о полноте исчисления высказываний. Доказательство выводимости формул методом резолюций.  Неклаузальное  правило  резолюций.	Понятие теории	первого	порядка.	Аксиомы		и	правила		вывода исчисления	предикатов,	непротиворечивость	и	полнота. Метод резолюций в теории предикатов.
Аксиоматические	теории	с	равенством.	Формальная арифметика.	
2.	Нечеткая  логика  и нечеткие множес-тва	Нечеткая логика, операции дизъюнкции, конъюнкции, отрицания и их свойства. Нечеткая импликация и эквиваленция, их свойства. Нечеткие множества и операции над ними	
3.	Рекурсивные функции	Понятие алгоритмической системы. Понятие примитивно рекурсивной функции. Примитивная рекурсивность функций сложения,  умножения,  усеченной  разности  и  знака  числа.
Примитивная рекурсивность предикатов равенства и неравенства, условная функция. Теорема о примитивной рекурсивности ограниченной суммы, произведения, кванторов. Теорема об ограниченном операторе наименьшего	

		аргумента.   Теорема   об   операторе   совместной   рекурсии. Частично-рекурсивные	функции,	тезис	Черча.
Общерекурсивные функции, функция Аккермана.	
4.	Машины Тьюринга	Определение машины Тьюринга, примеры. Транспозиция и копирование чисел машинами Тьюринга. Представление чисел и вычисление функций машинами Тьюринга, примеры вычисления $Z(x)$, $N(x)$. Композиция машин Тьюринга, примеры циклического сдвига, копирования $n$ чисел и вычисление функций с сохранением аргументов. Правильное вычисление машинами Тьюринга селекторных функций и суперпозиции функций. Правильное вычисление функций, задаваемых оператором примитивной рекурсии. Вычисление функций, задаваемых неограниченным оператором наименьшего  значения.  Теорема  Тьюринга.  Универсальная
машина Тьюринга. Неразрешимость  проблемы останова.	
5.	Формальные языки и грамматики	Понятие формального языка, операции с ними. Понятие формальной грамматики, иерархия Хомского. Регулярные языки, теорема об их объединении. Теоремы о конкатенации и итерации регулярных языков. Понятие конечного автомата. Теоремы о распознавании регулярных языков конечными автоматами. Преобразования конечных автоматов. Контекстно свободные языки и грамматики. Стековые автоматы.	
6.	Сложность алгоритмов.	Понятие	сложности	алгоритма,		полиномиальная		и экспоненциальная	сложность,	классы	P	и	E.
Недетерминированная	машина	Тьюринга	и	класс	NP. Полиномиальная сводимость и NP-полнота.	

Практические/семинарские занятия

№	Наименование раздела /темы дисциплины	Содержание	
1.	Аксиоматические теории	Применение метода резолюций в исчислении высказываний и теории предикатов.	
2.	Нечеткая  логика  и нечеткие множества	Операции нечеткой логики. Нечеткие множества и операции над ними.	
3.	Рекурсивные функции	Выражение примитивно рекурсивных функций через основные примитивно рекурсивные функции. Ограниченные суммы, произведения, кванторы. Оператор наименьшего аргумента. Частично-рекурсивные функции.	
4.	Машины Тьюринга	Вычисление функций и предикатов машинами Тьюринга. Композиция машин Тьюринга.	
5.	Формальные языки и грамматики	Объединение, конкатенация и итерация регулярных языков. Распознавание регулярных языков конечными автоматами. Преобразования конечных автоматов	
6.	Сложность алгоритмов.	Примеры NP-полных задач.	

5.	Перечень учебно-методического обеспечения для самостоятельной работы обучающихся по дисциплине
1. Насыров А.З., Насыров З.Х. Математическая логика и теория алгоритмов. --- Обнинск: ИАТЭ,2003.
2.	Насыров З.Х. Сборник задач по дискретной математике. --- Обнинск: ИАТЭ, 2003.
3.	Насыров А.З., Насыров З.Х. Алгоритмы и их сложность. --- Обнинск: ИАТЭ, 2002.

6.	Фонд  оценочных  средств  для  проведения  промежуточной  аттестации обучающихся по дисциплине

6.1.	Паспорт фонда оценочных средств по дисциплине

№ п/п	Контролируемые разделы (темы) дисциплины (результаты по разделам)	Код контролируемой компетенции (или её части) / и ее
формулировка	Наименование оценочного средства	
1.	Аксиоматические теории	 ОПК-2	Контрольная работа №1, экзамен.	
2.	Нечеткая логика и нечеткие множества	ОПК-2	Контрольная работа №1, экзамен.	
3.	Рекурсивные функции.	ОПК-2	Контрольная работа №1, экзамен.	
4.	Машины Тьюринга	ОПК-2	Контрольная работа №2, экзамен.	
5.	Формальные языки и грамматики	ОПК-2	Контрольная работа №2, экзамен.	
6.	Сложность алгоритмов.	ОПК-2	Контрольная работа №2, экзамен.	

6.2.	Типовые контрольные задания или иные материалы

6.2.1.	Экзамен
а) типовые вопросы (образец)
1.Сформулировать и доказать теорему о двойном отрицании в исчислении высказываний.
2.	Построить машину Тьюринга $C$ для копирования одного числа.
3.	Сформулировать и доказать теорему об объединении регулярных языков.
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 40%, а элемент умения — в 60%/
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют 14, 13 и 13 баллов соответственно.

6.2.2.	Контрольная работа №1
а) типовые задания (образец)

Задание 1. \Используя метод резолюций докажите, что в исчислении высказываний $(\ol b\vee c\vee\ol d)(\ol b\vee\ol c\vee d)(\ol a\vee b\vee c) (\ol a\vee\ol c\vee d)\vdash \ol a\,\ol b\vee c\,d\vee b\,\ol c\,\ol d$.
Задание 2. Пусть A,B,C,D,E -- множества и даны нечеткие значения преди- катов \mu(x\in A)=0,2, \mu(x\in B)=0,4, \mu(x\in C)=0,5, \mu(x\in D)=0,1,
\mu(x\in E)=0,6 для некоторого элемента x. Найдите нечеткое значение
предиката $x\in M$, если $M=(\ol A+B)\cap(C\cdot(D^2\cup E))$. Задание 3. Представьте в виде суперпозиции основных примитивно рекурсивных функций функцию $f(x)$, заданную с помощью оператора
примитивной рекурсии так: f(0)=3, f(x+1)=f(x)+4\sg(5\ur x)+7\ol{\sg}(5\ur x).
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 30%, элемент умения — в 40%/, а элемент владения (навыка) – в 30%.
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют по 10 баллов.

6.2.3.	Контрольная работа №2
а) типовые задания (образец):
Задание 1 Напишите программу машины Тьюринга для вычисления функции
$y=x-\ol{\sg}|x-2|$.
Задание 2. Пусть даны машины Тьюринга $F$, $P$ и $Q$, вычисляющие функции $f(x,y,z)$, $p(x)$ и $q(x)$ соответственно без сохранения аргумента. Постройте машину Тьюринга $H$ для вычисления функции, заданной формулой $h(x)=f\bigl(p(q(x)),\,x,\,q(p(x))\bigr)$.
Задание 3. Для языка L=\{a^2,\,b^2c\}^+ найдите порождающую его регуляр- ную грамматику G и постройте конечный автомат K, воспринимающий L.
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 30%, элемент умения — в 40%/, а элемент владения (навыка) – в 30%.
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют по 10 баллов.

6.3. Методические материалы, определяющие процедуры оценивания знаний, умений, навыков и (или) опыта деятельности, характеризующих этапы формирования компетенций
Итоговый балл по дисциплине получается суммированием количества баллов набранных по каждой из 2 контрольных работ и баллов за экзамен. Оценка «отлично» ставится за 90 — 100 баллов, «хорошо» за 75 – 89 баллов, «удовлетворительно» за 60 – 74 балла,
«неудовлетворительно» за 0 —59 итоговых баллов.

7.	Перечень основной и дополнительной учебной литературы, необходимой для освоения дисциплины

а) основная учебная литература:
1	1.Герасимов А.С. Курс математической логики и теории вычислимости, учебное пособие, Лань, 2014. - адрес: www.e.lanbook.ru.
2	Глухов М.М., Шишков А.Б. Математическая логика. Дискретные функции. Теория алгоритмов, учебное пособие. Лань, 2012.   - адрес: www.e.lanbook.ru.

б) дополнительная учебная литература:
1.	Насыров А.З., Насыров З.Х. Математическая логика и теория алгоритмов. --- Обнинск: ИАТЭ,2003.
1.	Мальцев А.И. Алгоритмы и рекурсивные функции. --- М.:~Наука, 1965.
2.	Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. --- М.:~Наука, 1985.
3.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. --- М.:~Наука, 1992.
4.	Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. --- М.:~Наука, 1975.
5.	Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. --- Киев: Наукова думка, 1974.
6.	Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. --- Новосибирск: НГУ, 1995.
7.	Рейуорд-Смит В.Дж. Теория формальных языков. --- М.:~Радио и связь, 1988.
8.	Гулина О.М. Введение в теорию формальных языков. Учебное пособие по курсу "Языки и грамматики". --- Обнинск: ИАТЭ, 2000.
9.	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. --- М.:~Мир, 1982.
10.	Лорьер Ж.-Л. Системы искусственного интеллекта. --- М.:~Мир, 1991.
11.	Логический подход к искусственному интеллекту. --- М.:~Мир, 1990.}
12.	Насыров А.З., Насыров З.Х. Алгоритмы и их сложность. --- Обнинск: ИАТЭ, 2002.

8.	Перечень	ресурсов*	информационно-телекоммуникационной	сети
«Интернет» (далее - сеть «Интернет»), необходимых для освоения дисциплины
www.library.mephi.ru, www.e.lanbook.ru.

9.	Методические указания для обучающихся по освоению дисциплины

Вид учебного занятия	Организация деятельности студента	
Лекция	При изучении дисциплины следует иметь в виду, что этот раздел высшей математики очень бурно развивается и учебный материал в разных учебных пособиях может сильно отличаться и терминологически и по стилю изложения и по содержанию. Поэтому на первой стадии изучения следует придерживаться материала конспектов лекций и основной литературы. При желании более глубокого изучения можно знакомиться с материалом излагаемым в дополнительной литературе.	
Практические занятия	Для уверенности в правильности решения задачи полезно проверить ответ с помощью альтернативного решения или на частном случае.	
Контрольная работа	Изучить	методические	указания	по	решению	контрольных	задач	и потренироваться на решении аналогических задач.	
Подготовка к экзамену	При  подготовке  к  экзамену  необходимо  ориентироваться  на  конспекты лекций и рекомендуемую литературу	

10.	Перечень информационных технологий, используемых при осуществлении образовательного процесса по дисциплине, включая перечень программного обеспечения и информационных справочных систем (при необходимости)
Электронная библиотека НИЯУ МИФИ

11.	Описание материально-технической базы, необходимой для осуществления образовательного процесса по дисциплине
Учебная аудитория достаточной вместимости для потока (лекция) или группы (семинары), проектор и ноутбук.

12.	Иные сведения и (или) материалы

12.1.	Перечень образовательных технологий, используемых при осуществлении образовательного процесса по дисциплине
Часов в интерактивной форме – 10.
Планомерная организация последовательности лекций и практических занятий в сочетании с внеаудиторной работой студента. При изложении разделов даются указания на связь с учебным материалом других дисциплин учебного плана, а также практическими приложениями. Систематические индивидуальные консультации.
Интерактивный подход заключается в вовлечении присутствующих студентов в обсуждение рассматриваемых методов решения задачи выработку новых приемов в их решении.

12.2.	Формы организации самостоятельной работы обучающихся (темы, выносимые для самостоятельного изучения; вопросы для самоконтроля; типовые задания для самопроверки

Самостоятельная работа студентов состоит в выполнении домашних заданий в соответствии с темами практических занятий. Контроль осуществляется путем проверки на практических занятиях.

№	Тема самостоятельной работы	Литература	Число часов	
1	Аксиоматические теории	[3]	1	
2	Рекурсивные функции	[3]	1	
3	Формальные языки и грамматики	[3]	1	

12.3.	Краткий терминологический словарь
Не требуется.